Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code,
print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

• 00 - 0
  
• 01 - 1
  
• 11 - 3
  
• 10 - 2

题目大意：给定数字n，代表n个比特，返回格雷码序列，即相邻的两个数只相差一个比特

题目难度：Medium

import java.util.*;
/**
 * Created by gzdaijie on 16/6/4
 * 思路,0 => [0]
 * 1 => 0 << 1 + 0, 0 << 1 + 1 => [0, 1]
 * 2 => 0 << 1 + 0, 0 << 1 + 1, 1 << 1 + 1 , 1 << 1 + 0 = > [0,1,3,2]
 * 即每次在上一次的结果后面依次添加0,1,1,0,0,1,1....
 * 时间复杂度O(2^0 + 2^1 + 2^2 + ... + 2^n ) = O(2^N)
 */
public class Solution {
    public List<Integer> grayCode(int n) {
        Queue<Integer> result = new LinkedList<>();

        result.add(0);
        for (int i = 0; i < n; i++) {
            int tag = 0;
            int size = result.size();
            while (size-- > 0) {
                int top = result.poll();
                result.add((top << 1) + tag); // 这里tag与上一循环的tag相同
                tag ^= 1;  // tag 0变1,或1变0
                result.add((top << 1) + tag);
            }
        }
        return (List<Integer>)result;
    }
}